Date modified: Thu 2024-03-14 . 03:36 PM
Date created: Thu 2024-02-22 . 10:19 AM
# A01 A brief word on mathematical statements and proofs. ## True, false, and vacuously true. Quite often you will need to decide whether a mathematical statement is true or false. Let us look at a specific scenario. Suppose you have a statement $S$ that claims "all objects in $X$ has property $P$". If you find any one object $x$ in $X$ that fails property $P$, then you have disproved this statement $S$, and you can conclude that statement $S$ is **false**. This $x$ you found is called a **counterexample** to the statement $S$.  If you want to show $S$ is true, however, you need to show **every object in $X$ possesses the property $P$.** Now we have a "curious" edge case: What if $X$ is empty, that there is no object in the set $X$? What can we say about our statement $S$? Well in this case statement $S$ is **true.** This is known as **vacuously true**, and we say that $S$ is a **vacuously true statement**. Why? To check the validity of $S$, we need to check whether everything in $X$ has property $P$. Well, since there is nothing to check as $X$ is empty, we are done! We didn't reach any contradiction at all. So we deem statement $S$ to be true. As a curious example. Let us consider the statement "all elephants in the classroom last Wednesday morning can fly." Is this statement true or false? Well actually it depends! - If on last Wednesday morning, there is no elephant in the classroom, then this statement is true, and in fact vacuously true. Since there is no elephants to check, we are done, and the statement passes as true. - If on last Wednesday morning, there is an elephant in the classroom, and (reasonably) we know this elephant cannot fly, then this statement is false. ## Characterization. In math, when two statements $P$ and $Q$ are logically equivalent, that $P \iff Q$, that $P$ if and only if $Q$, then we say $Q$ is a characterization of $P$ (and vice versa). ## How to show two sets are the same? To show two sets $A,B$ are equal, one should establish **mutual containment**, as we have the following characterization of set equality: > For $A,B$ two sets, we have $A=B$ if and only if both $A\subset B$ and $B\subset A$. ## How to prove a statement using contradiction? Suppose you want to prove a statement that looks like this: "If $P$ then $Q$", where $P,Q$ are some statements. To approach it via contradiction is do the following: > Assume $P$ and assume to the contrary not $Q$. ....Some work that leads to not $P$. And since not $P$ contradicts $P$ that we assumed, this means not $Q$ is false. Hence $Q$ is true.